package com.chj.zhongji.class04;

public class Code05_LCSubsequence {

	public static String lcse(String str1, String str2) {
		if (str1 == null || str2 == null || str1.equals("") || str2.equals("")) {
			return "";
		}
		char[] chs1 = str1.toCharArray();
		char[] chs2 = str2.toCharArray();
		int[][] dp = getdp(chs1, chs2);

		printMatrix(dp);

		int m1 = chs1.length - 1;
		int n = chs2.length - 1;
		char[] res = new char[dp[m1][n]];
		for (int i = 0; i < res.length; i++) {
			System.out.println(i + "----" + res[i]);
		}
		int index = res.length - 1;
		System.out.println(index + "--index--" + res.length);
		while (index >= 0) {
			if (n > 0 && dp[m1][n] == dp[m1][n - 1]) {
				n--;
			} else if (m1 > 0 && dp[m1][n] == dp[m1 - 1][n]) {
				m1--;
			} else {
				System.out.println(n + "--mmm--" + chs1[m1]);
				System.out.println(m1 + "--mmm--" + chs1[m1]);
				res[index--] = chs1[m1];
				m1--;
				n--;
			}
		}
		return String.valueOf(res);
	}

	public static int[][] getdp(char[] str1, char[] str2) {
		int[][] dp = new int[str1.length][str2.length];
		dp[0][0] = str1[0] == str2[0] ? 1 : 0;
		for (int i = 1; i < str1.length; i++) {
			dp[i][0] = Math.max(dp[i - 1][0], str1[i] == str2[0] ? 1 : 0);
		}
		System.out.println("-----111-------");
		printMatrix(dp);
		System.out.println("-----111-------");
		for (int j = 1; j < str2.length; j++) {
			dp[0][j] = Math.max(dp[0][j - 1], str1[0] == str2[j] ? 1 : 0);
		}
		System.out.println("-----222-------");
		printMatrix(dp);
		System.out.println("-----222-------");
		for (int i = 1; i < str1.length; i++) {
			for (int j = 1; j < str2.length; j++) {
				dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				if (str1[i] == str2[j]) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
				}
			}
		}
		return dp;
	}

	// for test
	public static void printMatrix(int[][] matrix) {
		for (int i = 0; i != matrix.length; i++) {
			for (int j = 0; j != matrix[0].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
//		String str1 = "A1BC2D3EFGH45I6JK7LMN";
//		String str2 = "12OPQ3RST4U5V6W7XYZ";

		String str1 = "A1B2C";
		String str2 = "12OPQ";
		System.out.println(lcse(str1, str2));

	}
}
